BOJ_2295_세수의 합

집합에서 세 숫자의 합이 집합의 원소로 들어있는지 확인하는 문제

이 문제의 핵심은
x + y + z = k일 때 x + y = k - z 인 것을 이용해서 푸는 것이다

2가지 풀이법이 있다

이분탐색을 활용

이분 탐색(Binary Search)을 사용할 경우
로직의 순서는 다음과 같다

  1. x + y, 즉 집합의 두 수를 더한 합 배열을 저장한다
  2. 집합 배열, 합 배열을 정렬한다
  3. 중첩 반복문을 돌면서 k - z, 즉 집합의 어떤 큰 수 - 집합의 어떤 작은 수를 했을 때
    합 배열 안에 해당 값이 있는지 본다. 이 과정에서 이분 탐색을 활용한다
import sys

def binary_search():  
    input_ = sys.stdin.readline  
  
    n = int(input_())  
    nums = []  
  
    for _ in range(n):  
        nums.append(int(input_()))  
    nums.sort()  
  
    n_sum = []  
    for i in range(n):  
        for j in range(i, n):  
            n_sum.append(nums[i] + nums[j])  
    n_sum.sort()  
  
    for i in range(n - 1, -1, -1):  
        for j in range(i):  
            target = nums[i] - nums[j]  
            start = 0  
            end = len(n_sum) - 1  
  
            while start < end:  
                mid = start + (end - start) // 2  
  
                if n_sum[mid] < target:  
                    start = mid + 1  
                else:  
                    end = mid  
  
            if n_sum[start] == target:  
                print(nums[i])  
                return  
  
  
binary_search()

Set을 활용

또 다른 풀이법으로는 hashSet을 사용하는 게 있다

이분탐색에 비해 직관적인 풀이이다

  1. 두 수의 합을 set에 저장한다
  2. k - z, 즉 집합의 어떤 큰 수 - 집합의 어떤 작은 수가 set에 포함되어 있는지 확인한다
import sys  
  
  
# # set을 이용한 풀이  
input_ = sys.stdin.readline  
N = int(input_())  
arr = [int(input_()) for _ in range(N)]  
arr.sort()  
  
arr_sum = set()  
for x in arr:  
    for y in arr:  
        arr_sum.add(x + y)  
  
  
def check():  
    for i in range(N - 1, -1, -1):  
        for j in range(i + 1):  
            if arr[i] - arr[j] in arr_sum:  
                print(arr[i])
                return  
  
check()
비교

위 : Set
아래 : 이분탐색

캡처.png